perm filename SMLBK1.PAL[HAL,HE] blob
sn#155557 filedate 1975-04-24 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .SBTTL Small block allocator: GTITEM
C00009 ENDMK
C⊗;
.SBTTL Small block allocator: GTITEM
;Coded by RF, 10-Sept-1974
;For small items like value cells, typically ranging in size
;from 1 to 20 words, many of which are needed, there is a
;small block allocator. Sixteen items of like size are
;allocated simultaneously with GTFREE when needed. SZHH points
;to a the size header for the smallest size currently being
;used. (One efficiency not currently programmed in is
;to have this initially point to a size header for an impossible
;large size item.) Each size has its own header, pointing
;down a list of small blocks which have been allocated for this
;size. Each block holds the 16 items.
;Global, pointing to smallest size header.
SZHH: .BLKW 1 ;Size header Header.
;Size header. Each small block size has one of these.
II == 0
XX NXTSH ;Next size header, for bigger blocks. (Must be first field)
XX SIZE ;Size of item in small block in WORDS.
XX NALLOC ;Number of allocated blocks.
XX BLKLST ;Points to first small block of this size.
SIZSH = II/2 ;How long a size header is in WORDS.
;Small block. Each one holds 16 items, as well as this info:
II == 0
XX NEXTB ;Next block of this size. (Must be first field)
XX MASK ;Each bit for one item. 0=free; 1=busy.
XX FRBIT ;Rotating bit. Points to last assigned place.
XX WORD0 ;First word of 16*SIZE words.
SIZBLH = II/2 ;How long a block header is in WORDS.
;Routine to allocate an item of size R0 words. Returns location
; of item found in R0.
GTITEM: MOV R2,-(SP) ;Save R2.
MOV R3,-(SP) ;Save R3.
MOV #SZHH,R3 ;R3 ← LOC[SZHH]. Used to link in new.
MOV NXTSH(r3),R1 ;R1 ← LOC[first size header]
BEQ GTNWSH ;If 0, then need new size header.
GT1: MOV SIZE(R1),R2 ;R2 ← size of current size header in words.
CMP R2,R0 ;Is this the size we want?
BEQ GTSZFD ;Yes. We found the size.
BGT GTNWSH ;No, too large. Need new size header.
MOV R1,R3 ;No, too small. R3 ← LOC[too small size header]
MOV NXTSH(R1),R1 ;R1 ← LOC[next size header]
BNE GT1 ;If there is one, try again.
GTNWSH: MOV R0,-(SP) ;Save R0.
MOV R1,-(SP) ;Save R1.
MOV #SIZSH,R0 ;R0 ← Number of words needed for a size header.
JSR PC,GTFREE ;Get a block of that size.
MOV R0,R1 ;R1 ← LOC[new size header]
MOV (SP)+,NXTSH(R1) ;NXTSH[new size header] ← LOC[next size header]
MOV R1,NXTSH(R3);NXTSH[previous size header] ← LOC[new size header]
MOV (SP)+,R0 ;Restore R0 ← size desired in words.
MOV R0,SIZE(R1) ;SIZE[new size header] ← correct size
CLR NALLOC(R1) ;NALLOC[new size header] ← 0
CLR BLKLST(R1) ;BLKLST[new size header] ← 0
;At this point, we have found a size header of the right size.
;R0 = size, R1 = LOC[size header found]
GTSZFD: ROL R0 ;R0 ← desired size in BYTES.
MOV BLKLST(R1),R3;R3 ← LOC[block to try]
BEQ GTNWBL ;If no more blocks, then get a new one.
GT5: CMP #-1,MASK(R3);Is this block full?
BNE GDBLK ;No. Can use it.
MOV NEXTB(R3),R3;Yes. Get another block.
BNE GT5 ;If there is one, try it.
GTNWBL: ROL R0 ;Else need new block.
ROL R0 ;Recall: R0 = 2*SIZE (since in bytes)
ROL R0 ;R0 ← 20*SIZE words
ADD #SIZBLH,R0 ;R0 ← Size of block we need.
MOV R1,R2 ;R1 will be clobbered soon. R2 ← LOC[size header].
JSR PC,GTFREE ;R0 ← LOC[new block]
MOV BLKLST(R2),NEXTB(R0);NEXTB[block just made] ← LOC[first old block]
MOV R0,BLKLST(R2);BLKLST[size header] ← LOC[block just made]
INC NALLOC(R2) ;Just allocated a new block.
MOV #100000,FRBIT(R0);Set its FRBIT arbitrarily.
MOV FRBIT(R0),MASK(R0);We will assign this item to caller.
ADD #WORD0,R0 ;R0 ← LOC[new item]
BR GTRET ;Prepare to return.
GDBLK: ROR FRBIT(R3) ;Set FRBIT to next item.
BIT FRBIT(R3),MASK(R3) ;Is this item available?
BNE GDBLK ;No. Try again.
BIS FRBIT(R3),MASK(R3) ;Yes. Set mask appropriately.
MOV R3,R2 ;
ADD #WORD0,R2 ;R2 ← LOC[first item in block]
MOV FRBIT(R3),R3;R3 ← FRBIT. We are about to calculate address of item.
BMI GT3 ;If R3 has 15 bit on, then R2 is right.
GT4: ADD R0,R2 ;Else R2 ← LOC[next item in block]
ROL R3 ;
BPL GT4 ;Try again.
GT3: MOV R2,R0 ;Almost done. R0 ← LOC[found item]
GTRET: MOV (SP)+,R3 ;Restore R3
MOV (SP)+,R2 ;Restore R2
RTS PC ;Done.